﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm.SortAlgorithm
{
    public static class IListLCS
    {
        /// <summary>
        /// 获取最长公共子序列
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="lst"></param>
        /// <param name="otherLst"></param>
        /// <returns></returns>
        public static T[] GetLCS<T>(this T[] lst, T[] otherLst) where T : IComparable<T>
        {
            var len1 = lst.Length;
            var len2 = otherLst.Length;

            double[,] c = new double[len1+1, len2 + 1];
            int[,] b = new int[len1+1, len2+1];
            for (int i = 1; i <= len1; i++)
            {
                c[i, 0] = 0;
            }

            for (int j = 0; j <= len2; j++)
            {
                c[0, j] = 0;
            }

            for (int i = 1; i <= len1; i++)
            {
                for (int j = 1; j <= len2; j++)
                {
                    if(lst[i-1].CompareTo(otherLst[j-1])==0)
                    {
                        c[i, j] = c[i - 1, j - 1] + 1;
                        b[i, j] = 0;
                    }
                    else if (c[i - 1, j] >= c[i, j - 1])
                    {
                        c[i, j] = c[i - 1, j];
                        b[i, j] = 1;
                    }
                    else
                    {
                        c[i, j] = c[i, j - 1];
                        b[i, j] = -1;
                    }
                }
            }

            return getLcs<T>(b, lst, lst.Length, otherLst.Length);
        }

        private static T[] getLcs<T>(int[,] b, T[] x, int lenx, int leny)
        {
            if (lenx == 0 || leny == 0)
            {
                return new T[0];
            }
            List<T> result = new List<T>();
            if (b[lenx, leny] == 0)
            {
                result.AddRange(getLcs<T>(b, x, lenx - 1, leny-1));
                result.Add(x[lenx-1]);
            }
            else if (b[lenx, leny] == 1)
            {
                result.AddRange(getLcs<T>(b, x, lenx - 1, leny));
            }
            else
            {
                result.AddRange(getLcs<T>( b,x,lenx ,leny -1));
            }
            return result.ToArray();
        }
    }
}
